BOJ_2151_거울 설치

다익스트라(Dijkstra) 알고리즘을 활용해서 거울을 최소 개수로 설치하는 문제

PGMS_67259_경주로 건설과 매우 유사하다!
dis(여기서는 visited) 배열을 3차원으로 구성해서 각 진로 방향에 따라 비용을 계산해야 한다

거울을 만나면 이 다음 진로에서 2가지 방향으로 이동할 수 있다
예를 들어 오른쪽 방향으로 진행되던 빛은, 거울을 만나 위/아래로 진로를 바꿀 수 있다

로직의 흐름은 이렇다

1. dis 배열을 INS 값으로 초기화 한다
2. 문의 위치를 파악한 후 가능한 진행 방향을 heapq에 넣는다
3. 거울의 개수를 기준으로 정렬해가며 반대쪽 문을 찾는다

import sys  
from heapq import heappush, heappop  
  
dx = [0, 0, -1, 1]  
dy = [-1, 1, 0, 0]  
  
dir_dict = dict()  
dir_dict[(0, -1)] = 0  
dir_dict[(0, 1)] = 1  
dir_dict[(-1, 0)] = 2  
dir_dict[(1, 0)] = 3  
  
N = int(input())  
room = [list(input()) for _ in range(N)]  
visited = [[[sys.maxsize] * 4 for _ in range(N)] for _ in range(N)]  
hq = []  
start = (0, 0)  
# 문부터 문까지 최소 거울 설치 개수  
flag = False  
for i in range(N):  
    if flag:  
        break  
    for j in range(N):  
        if not flag and room[i][j] == '#':  
            start = (i, j)  
            # 사방 탐색  
            for k in range(4):  
                nx = i + dx[k]  
                ny = j + dy[k]  
  
                if nx < 0 or ny < 0 or nx >= N or ny >= N:  
                    continue  
  
                if room[nx][ny] != '*':  
                    dxx = dx[k]  
                    dyy = dy[k]  
                    flag = True  
                    heappush(hq, (0, i, j, dx[k], dy[k]))  
  
while hq:  
    count, x, y, dxx, dyy = heappop(hq)  
    v = dir_dict[(dxx, dyy)]  
    visited[x][y][v] = count  
  
    if room[x][y] == '#' and not (x == start[0] and y == start[1]):  
        # 골인  
        print(count)  
        break  
  
    nx = x + dxx  
    ny = y + dyy  
  
    if nx < 0 or ny < 0 or nx >= N or ny >= N:  
        continue  
  
    if room[nx][ny] == '*':  
        continue  
  
    if visited[nx][ny][v] > count:  
        heappush(hq, (count, nx, ny, dxx, dyy))  
  
    if room[nx][ny] == '!':  
        # 방향 꺾기  
        new_dx = -1 * dyy  
        new_dy = -1 * dxx  
  
        v = dir_dict[(new_dx, new_dy)]  
        if visited[nx][ny][v] > count + 1:  
            heappush(hq, (count + 1, nx, ny, new_dx, new_dy))  
  
        new_dx *= -1  
        new_dy *= -1  
  
        v = dir_dict[(new_dx, new_dy)]  
        if visited[nx][ny][v] > count + 1:  
            heappush(hq, (count + 1, nx, ny, new_dx, new_dy))